| 翻訳と辞書 |
| Gallai–Hasse–Roy–Vitaver theorem ： ウィキペディア英語版 |
Gallai–Hasse–Roy–Vitaver theorem
In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that a number ''k'' is the smallest number of colors among all colorings of graph ''G'' if and only if ''k'' is the largest number for which every orientation of ''G'' contains a simple directed path with ''k'' vertices.〔.〕 That is, the chromatic number is one plus the length of a longest path in an orientation of the graph chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.〔.〕
An alternative statement of the same theorem is that every orientation of a graph with chromatic number ''k'' contains a simple directed path with ''k'' vertices;〔.〕 this path can be constrained to begin at any vertex that can reach all other vertices of the oriented graph.〔.〕〔.〕
==Examples==
A bipartite graph may be oriented from one side of the bipartition to the other; the longest path in this orientation has only two vertices. Conversely, if a graph is oriented without any three-vertex paths, then every vertex must either be a source (with no incoming edges) or a sink (with no outgoing edges) and the partition of the vertices into sources and sinks shows that it is bipartite.
In any orientation of a cycle graph of odd length, it is not possible for the edges to alternate in orientation all around the cycle, so some two consecutive edges must form a path with three vertices. Correspondingly, the chromatic number of an odd cycle is three.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Gallai–Hasse–Roy–Vitaver theorem」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|